#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
#include <iostream>
#include <sys/mman.h>
#include <unistd.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <unistd.h>

#define THREAD_COUNT 8
#define fi first
#define se second
#define pii pair<int, int>
using namespace std;
const int N = 3e6 + 5;
const int M = 6e5 + 5;
const char numchar[10] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
//namespace fastIO {
//#define BUF_SIZE 100000
//#define OUT_SIZE 100000
//#define ll long long
//    bool IOerror = 0;
//
//    inline char nc() {
//        static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
//        if (p1 == pend) {
//            p1 = buf;
//            pend = buf + fread(buf, 1, BUF_SIZE, stdin);
//            if (pend == p1) {
//                IOerror = 1;
//                return -1;
//            }
//        }
//        return *p1++;
//    }
//
//    inline bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
//
//    inline bool read(int &x) {
//        bool sign = 0;
//        char ch = nc();
//        x = 0;
//        for (; blank(ch); ch = nc());
//        if (IOerror)return false;
//        if (ch == EOF) return false;
//        if (ch == '-')sign = 1, ch = nc();
//        for (; ch >= '0' && ch <= '9'; ch = nc())x = x * 10 + ch - '0';
//        if (sign)x = -x;
//        return true;
//    }
//
//    struct Ostream_fwrite {
//        char *buf, *p1, *pend;
//
//        Ostream_fwrite() {
//            buf = new char[BUF_SIZE];
//            p1 = buf;
//            pend = buf + BUF_SIZE;
//        }
//
//        void out(char ch) {
//            if (p1 == pend) {
//                fwrite(buf, 1, BUF_SIZE, stdout);
//                p1 = buf;
//            }
//            *p1++ = ch;
//        }
//
//        void out(string ch) {
//            if (p1 == pend) {
//                fwrite(buf, 1, BUF_SIZE, stdout);
//                p1 = buf;
//            }
//            for (int i = 0; i < ch.size(); ++i)
//                *p1++ = ch[i];
//        }
//
//        void print(int x) {
//            static char s[15], *s1;
//            s1 = s;
//            if (!x)*s1++ = '0';
//            if (x < 0)out('-'), x = -x;
//            while (x)*s1++ = x % 10 + '0', x /= 10;
//            while (s1-- != s)out(*s1);
//        }
//
//        void print(char *s) { while (*s)out(*s++); }
//
//        void println(char *s) {
//            while (*s)out(*s++);
//            out('\n');
//        }
//
//        void flush() {
//            if (p1 != buf) {
//                fwrite(buf, 1, p1 - buf, stdout);
//                p1 = buf;
//            }
//        }
//
//        ~Ostream_fwrite() { flush(); }
//    } Ostream;
//
//    inline void print(int x) { Ostream.print(x); }
//
//    inline void print(char x) { Ostream.out(x); }
//
//    inline void print(string x) { Ostream.out(x.c_str()); }
//
//    inline void println(int x) {
//        Ostream.print(x);
//        Ostream.out('\n');
//    }
//
//    inline void printd(int x) {
//        Ostream.print(x);
//        Ostream.out(',');
//    }
//
//    inline void println(char x) {
//        Ostream.out(x);
//        Ostream.out('\n');
//    }
//
//    inline void print(char *s) { Ostream.print(s); }
//
//    inline void println(char *s) { Ostream.println(s); }
//
//#undef ll
//#undef OUT_SIZE
//#undef BUF_SIZE
//};
//using namespace fastIO;

struct Result {
    int (*ans)[8] = new int[N][8];
    int *len = new int[N];
    int num;
};

struct G_Edge {
    struct Edge {
        int v, next;
    } edge[M];

    int head[M], cnt;

    void init(int n) {
        if (cnt != 0) n = cnt;
        cnt = 0;
        memset(head, -1, sizeof(int) * n);
    }

    void add(int u, int v) {
        edge[cnt] = {v, head[u]};
        head[u] = cnt++;
    }
};

struct find_huan {
    bool flag[M], *can;
    int cur[15], is[M], f[M], dis[M], que[M];
    int _head, _tail, m, n;
    pii *p;
    G_Edge *G;

    void init(int _n, int _m, bool *_can, pii *_p, G_Edge *_G) {
        n = _n;
        m = _m;
        can = _can;
        p = _p;
        G = _G;
    }

    inline void add_ans(int now_len, Result *result) {
        result->ans[result->num][1] = cur[1];
        result->ans[result->num][2] = cur[2];
        result->ans[result->num][3] = cur[3];
        if (now_len == 3) return;
        result->ans[result->num][4] = cur[4];
        if (now_len == 4) return;
        result->ans[result->num][5] = cur[5];
        if (now_len == 5) return;
        result->ans[result->num][6] = cur[6];
        if (now_len == 6) return;
        result->ans[result->num][7] = cur[7];
    }


    void dfs(int u, int step, int rt, Result *result) {
        if (u < rt || flag[u]) return;
        if (step > 4 && (is[u] != rt || 8 - step < dis[u])) return;
        cur[step] = u;
        if (step >= 3 && f[u] == rt) {
            result->len[++(result->num)] = step;
            add_ans(step, result);
        }
        if (step >= 7) return;
        flag[u] = true;
        int stp = step + 1;
        for (int i = G[0].head[u]; ~i; i = G[0].edge[i].next) {
            dfs(G[0].edge[i].v, stp, rt, result);
        }
        flag[u] = false;
    }


    void bfs(int rt) {
        while (_tail > _head) {
            int u = que[++_head];
            if (dis[u] == 3) continue;
            for (int i = G[2].head[u]; ~i; i = G[2].edge[i].next) {
                int v = G[2].edge[i].v;
                if (is[v] == rt || v < rt) continue;
                is[v] = rt;
                dis[v] = dis[u] + 1;
                que[++_tail] = v;
            }
        }
    }

    void start(int l, int r, Result *result) {
        if (l > r) return;
        for (int i = l; i <= r; i++) {
            if (!can[i]) continue;
            cur[1] = i;
            bool ok = false;
            is[i] = i;
            _head = _tail = 0;
            for (int j = G[1].head[i]; ~j; j = G[1].edge[j].next) {
                ok = true;
                int v = G[1].edge[j].v;
                f[v] = is[v] = i;
                dis[v] = 1;
                que[++_tail] = v;
            }

            if (ok) {
                bfs(i);
                dfs(i, 1, i, result);
            }
        }
    }
};

struct tag_mmap {
    // 要读取源文件的起始内存位置
    void *r_mem;
    // 要写入目标文件的起始内存位置
    void *w_mem;
    // 要复制的大小
    unsigned long long m_size;
};

inline void pr(string *num_string, int *d, int *now_len, string *ans) {
    *ans += num_string[d[1]];
    *ans += ',';
    *ans += num_string[d[2]];
    *ans += ',';
    if (*now_len == 3) {
        *ans += num_string[d[3]];
        *ans += '\n';
        return;
    }
    *ans += num_string[d[3]];
    *ans += ',';
    if (*now_len == 4) {
        *ans += num_string[d[4]];
        *ans += '\n';
        return;
    }
    *ans += num_string[d[4]];
    *ans += ',';
    if (*now_len == 5) {
        *ans += num_string[d[5]];
        *ans += '\n';
        return;
    }
    *ans += num_string[d[5]];
    *ans += ',';
    if (*now_len == 6) {
        *ans += num_string[d[6]];
        *ans += '\n';
        return;
    }
    *ans += num_string[d[6]];
    *ans += ',';
    *ans += num_string[d[7]];
    *ans += '\n';
}

bool cmp(pii a, pii b) {
    return a.se > b.se;
}

inline string numtostring(int x) {
    string tmp = "";
    if (x == 0) {
        return "0";
    }
    while (x != 0) {
        tmp += numchar[x % 10];
        x /= 10;
    }
    if (tmp.size() == 1)return tmp;
    reverse(tmp.begin(), tmp.end());
    return tmp;
}

void prtime(char *pos, timeval &time) {
    printf("%s=", pos);
    struct timeval now;
    gettimeofday(&now, NULL);
    printf("%dms\n", int((now.tv_sec * 1000 + now.tv_usec / 1000) - (time.tv_sec * 1000 + time.tv_usec / 1000)));
    time = now;
}

void find_thread(int n, int m, bool *can, pii *p, G_Edge *G, int l, int r, Result *result) {
    find_huan *F = new find_huan[1];
    F[0].init(n, m, can, p, G);
    F[0].start(l, r, result);
}

//多线程拷贝
void threadfunc(tag_mmap arg) {
    char *r = (char *) arg.r_mem;
    char *w = (char *) arg.w_mem;
    memcpy(w, r, arg.m_size);
}

void add_ans_thread(Result *result, string *ans, int j, string *num_string) {
    for (int k = 0; k < THREAD_COUNT; ++k)
        for (int i = 1; i <= result[k].num; i += 4) {
//            if (*((result + k)->len + i) == j) pr(num_string, *((result + k)->ans + i), &j, ans);
//            if (*((result + k)->len + i + 1) == j) pr(num_string, *((result + k)->ans + i + 1), &j, ans);
//            if (*((result + k)->len + i + 2) == j) pr(num_string, *((result + k)->ans + i + 2), &j, ans);
//            if (*((result + k)->len + i + 3) == j) pr(num_string, *((result + k)->ans + i + 3), &j, ans);
            if (result[k].len[i] == j) pr(num_string, result[k].ans[i], &j, ans);
            if (result[k].len[i + 1] == j) pr(num_string, result[k].ans[i + 1], &j, ans);
            if (result[k].len[i + 2] == j) pr(num_string, result[k].ans[i + 2], &j, ans);
            if (result[k].len[i + 3] == j) pr(num_string, result[k].ans[i + 3], &j, ans);
        }
}

int main() {
    timeval start;
    gettimeofday(&start, NULL);
    char *inputfile = "./data/1406671/test_data.txt";
    char *outputfile = "./z.out";
//    char *inputfile = "/data/test_data.txt";
//    char *outputfile = "/projects/student/output.txt";
    int m = 0, n = 0;
    int *val = new int[M];
    bool *can = new bool[M];
    pii *p = new pii[M];
    G_Edge *G = new G_Edge[3];
    unordered_map<int, int> mp;
    string *num_string = new string[M];

    //mmap读文件开始
    char *data = NULL;
    int fd = open(inputfile, O_RDONLY);
    long size = lseek(fd, 0, SEEK_END);
    data = (char *) mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
    int u, v, cost;
    int tmp = 0;
    int i = 0, j = 0;
    while (data[i] != '\0') {
        if (data[i] >= '0' && data[i] <= '9') {
            tmp *= 10;
            tmp += data[i] - '0';
        } else if (data[i] == ',') {
            if (j == 0) {
                u = tmp;
                j++;
            } else if (j == 1) {
                v = tmp;
                p[++m] = {u, v};
                val[++n] = u;
                val[++n] = v;
            }
            tmp = 0;
        } else {
            //cost = tmp;
            //printf("%d\n", w);
            j = 0;
            tmp = 0;
        }
        ++i;
    }
    //mmap读文件结束
//
    // 离散化
    sort(val + 1, val + n + 1);
    n = unique(val + 1, val + n + 1) - val - 1;
    for (int i = 1; i <= n; i++) mp[val[i]] = i;
    sort(p + 1, p + m + 1, cmp);
    for (int i = 1; i <= n; i++) {
        num_string[i] = numtostring(val[i]);
    }
    G[0].init(n + 5);
    G[1].init(n + 5);
    G[2].init(n + 5);
    for (int i = 1; i <= m; i++) {
        int u = mp[p[i].fi];
        int v = mp[p[i].se];
        if (u < v) can[u] = true;
        G[0].add(u, v);
        G[2].add(v, u);
        if (u > v)
            G[1].add(v, u);
    }
    //开始找环
//    find_huan* F = new find_huan[THREAD_COUNT];
//    F[0].init(n, m, val, can, p, G);
//    F[0].start(1, m);
//    int num = F[0].num;
    /*  结束  */
//    timeval time;
//    gettimeofday(&time, NULL);
    int num = 0;
    string ansstring = "";
    ansstring.reserve(90000000);
    const int nCount = n / THREAD_COUNT;
    if (nCount < 3) {
        //单线程
        Result *result = new Result[1];
        find_thread(n, m, can, p, G, 1, n, result);
        num += result->num;
        ansstring += numtostring(num);
        ansstring += '\n';
        for (int i = 3; i <= 7; i++) {
            int tmp = result->num;
            for (int j = 1; j <= tmp; j += 4) {
                if (result[0].len[j] == i) pr(num_string, result[0].ans[j], &i, &ansstring);
                if (result[0].len[j + 1] == i) pr(num_string, result[0].ans[j + 1], &i, &ansstring);
                if (result[0].len[j + 2] == i) pr(num_string, result[0].ans[j + 2], &i, &ansstring);
                if (result[0].len[j + 3] == i) pr(num_string, result[0].ans[j + 3], &i, &ansstring);
            }
        }
        int wfd;
        wfd = open(outputfile, O_RDWR | O_CREAT | O_TRUNC, 0666);
        lseek(wfd, ansstring.length() - 1, SEEK_SET);
        write(wfd, "\0", 1);
        void *w_mem = mmap(NULL, ansstring.length(), PROT_WRITE, MAP_SHARED, wfd, 0);
        memcpy(w_mem, ansstring.c_str(), ansstring.length());
        munmap(w_mem, ansstring.length());
        return 0;
    } else {
        //多线程
        std::thread threads[THREAD_COUNT];
        Result *result = new Result[THREAD_COUNT];

        for (int i = 0; i < THREAD_COUNT; i++) {
            int s, t;
            if (i < THREAD_COUNT - 1) {
                s = i * nCount + 1;
                t = (i + 1) * nCount;
            } else {
                s = i * nCount + 1;
                t = n;
            }
            threads[i] = std::thread(find_thread, n, m, can, p, G, s, t, result + i);
        }
        for (int i = 0; i < THREAD_COUNT; ++i) {
            threads[i].join();
        }
        for (int i = 0; i < THREAD_COUNT; ++i)num += result[i].num;


        string thread_ans[5];
        ansstring += numtostring(num);
        ansstring += '\n';
//        prtime("找环时间", time);
        std::thread add[5];
        for (int i = 0; i < 5; i++) {
            add[i] = thread(add_ans_thread, result, thread_ans+i, i + 3, num_string);
        }
        for (int i = 0; i < 5; i++) {
            add[i].join();
        }
//        prtime("拼接答案时间", time);
        int totallen = ansstring.length();
        for (int i = 0; i < 5; ++i)totallen += thread_ans[i].size();
        ansstring.reserve(totallen);
        for (int i = 0; i < 5; i++) {
            ansstring += thread_ans[i];
        }
//        prtime("拼接答案时间2", time);
        //多线程mmap输出
        int wfd;
        wfd = open(outputfile, O_RDWR | O_CREAT | O_TRUNC, 0666);
        lseek(wfd, ansstring.length() - 1, SEEK_SET);
        write(wfd, "\0", 1);
        const long long nCount = ansstring.length() / THREAD_COUNT;
        const long long nPages = nCount - (nCount % 4096);
        const long long nSplit = ansstring.length() - THREAD_COUNT * nPages;
        if (nCount < 4096) {
            void *w_mem = mmap(NULL, ansstring.length(), PROT_WRITE, MAP_SHARED, wfd, 0);
            memcpy(w_mem, ansstring.c_str(), ansstring.length());
            munmap(w_mem, ansstring.length());
        } else {
            struct tag_mmap mm[THREAD_COUNT];
            std::thread threads[THREAD_COUNT];
            for (int i = 0; i < THREAD_COUNT; ++i) {
                if (i < THREAD_COUNT - 1) {
                    mm[i].r_mem = (void *) (ansstring.c_str() + i * nPages);
                    mm[i].w_mem = mmap(NULL, nPages, PROT_WRITE, MAP_SHARED, wfd, i * nPages);
                    mm[i].m_size = nPages;
                    threads[i] = std::thread(threadfunc, mm[i]);
                } else {
                    mm[i].r_mem = (void *) (ansstring.c_str() + i * nPages);
                    mm[i].w_mem = mmap(NULL, nPages + nSplit, PROT_WRITE, MAP_SHARED, wfd, i * nPages);
                    mm[i].m_size = nPages + nSplit;
                    threads[i] = std::thread(threadfunc, mm[i]);
                }
            }
            for (int join = 0; join < THREAD_COUNT; join++) {
                threads[join].join();
            }
            for (int un = 0; un < THREAD_COUNT; un++) {
                munmap(mm[un].r_mem, mm[un].m_size);
                munmap(mm[un].w_mem, mm[un].m_size);
            }
        }
    }
//    prtime("输出时间", time);
    prtime("总时间 ", start);
    return 0;
}